package leetcode.year2021.month10;

/**
 * 32. 最长有效括号
 */
public class _22_01LongestValidParentheses32 {
  // 思路： 动态规划，需要求得动态规划方程，动态规划数组为，对应以i结尾的最长有效括号
  //  计算dp[i]的时候，如果 f(i) 为 '（'， dp[i]则为0
  //  如果f(i-1) 为'(' ,则dp[i] = dp[i-2] + 2
  //  如果f(i-1) 为')', 则dp[i] = dp[i-1] + dp[i-2-dp[i-1]] + 2


  public int longestValidParentheses(String s) {
    int[] dp = new int[s.length()];
    int maxLength = 0;

    for (int i = 1; i < s.length(); i++) {
      if (s.charAt(i) == ')'){
        if (s.charAt(i-1) == '('){
          dp[i] =( i-2 > 0 ? dp[i-2] : 0) + 2;
        } else if (i-1-dp[i-1] >= 0 && s.charAt(i-1-dp[i-1]) == '('){
          dp[i] = (i-2-dp[i-1] > 0 ? dp[i-2-dp[i-1]] : 0) + dp[i-1] + 2;
        }
        maxLength = Math.max(dp[i],maxLength);
      }
    }
    return maxLength;
  }

  /**
   * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：s = "(()"
   * 输出：2
   * 解释：最长有效括号子串是 "()"
   * 示例 2：
   *
   * 输入：s = ")()())"
   * 输出：4
   * 解释：最长有效括号子串是 "()()"
   * 示例 3：
   *
   * 输入：s = ""
   * 输出：0
   *
   */
}
